<!DOCTYPE html><html class="theme-next gemini use-motion" lang="zh-Hans"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1"><meta name="theme-color" content="#222"><script src="//cdn.bootcss.com/pace/1.0.2/pace.min.js"></script><link href="//cdn.bootcss.com/pace/1.0.2/themes/pink/pace-theme-flash.css" rel="stylesheet"><style>.pace .pace-progress{background:#1e92fb;height:3px}.pace .pace-progress-inner{box-shadow:0 0 10px #1e92fb,0 0 5px #1e92fb}.pace .pace-activity{border-top-color:#1e92fb;border-left-color:#1e92fb}</style><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css"><link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4"><link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.ico?v=5.1.4"><link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4"><link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222"><meta name="keywords" content="数据结构与算法,"><link rel="alternate" href="/atom.xml" title="It is written" type="application/atom+xml"><meta name="description" content="排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：  参考地址：https:&#x2F;&#x2F;www.runoob.com&#x2F;w3cnote&#x2F;t"><meta property="og:type" content="article"><meta property="og:title" content="数据结构与算法 (js版)  -- 排序"><meta property="og:url" content="http://king-xiyu.gitee.io/article/1a004747.html"><meta property="og:site_name" content="It is written"><meta property="og:description" content="排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：  参考地址：https:&#x2F;&#x2F;www.runoob.com&#x2F;w3cnote&#x2F;t"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geoqro1171j319o0sib0r.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger44efmwxj31450ggq8k.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geoqvb4uq3j317s0ownn1.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geor0u1lx6g30my075wqv.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geos1cerbbg30mj06w7l2.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geossx8k63g30mj0e113f.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geps5w4qi9j30xs11g1kx.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsevjny1j319i0x6e50.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger5o6v5whj30yg0hcgwf.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger5p2cnlhj30to0wi4ed.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger5puolrsj30tk0co455.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger5qyfuhuj317q0kknc3.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsljb9anj31ds0lkn0v.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsmj3pn4j30u805odid.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsuibhxrj30ji0i6myd.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepswvll78j31bg0iyacd.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsxxlsbyj31ao0jeacb.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gepsyd3qkuj31bs0ia41a.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gept1bkas5j31e00i6act.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gept231uwvj31as0hgq5m.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gept2cyyvij31ay0huwge.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1gept2qhx4cj30lq0j8wfl.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geptlnm66fg30s40fhdmw.gif"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geptmam205j30nw0dmahk.jpg"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger34e60kpg30s40fywic.gif"><meta property="og:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ger5g91o8oj30cw01wq2s.jpg"><meta property="article:published_time" content="2020-05-11T11:26:14.000Z"><meta property="article:modified_time" content="2020-09-01T00:45:13.955Z"><meta property="article:author" content="King-XiYu"><meta property="article:tag" content="数据结构与算法"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="http://ww1.sinaimg.cn/large/007WurYGgy1geoqro1171j319o0sib0r.jpg"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Gemini",version:"5.1.4",sidebar:{position:"left",display:"post",offset:12,b2t:!0,scrollpercent:!0,onmobile:!1},fancybox:!0,tabs:!0,motion:{enable:!0,async:!1,transition:{post_block:"fadeIn",post_header:"slideDownIn",post_body:"slideDownIn",coll_header:"slideLeftIn",sidebar:"slideUpIn"}},duoshuo:{userId:"0",author:"博主"},algolia:{applicationID:"",apiKey:"",indexName:"",hits:{per_page:10},labels:{input_placeholder:"Search for Posts",hits_empty:"We didn't find any results for the search: ${query}",hits_stats:"${hits} results found in ${time} ms"}}}</script><link rel="canonical" href="http://king-xiyu.gitee.io/article/1a004747.html"><title>数据结构与算法 (js版) -- 排序 | It is written</title><meta name="generator" content="Hexo 4.2.0"></head><body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans"><div class="container sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="header-inner"><div class="site-brand-wrapper"><div class="site-meta"><div class="custom-logo-site-title"><a href="/" class="brand" rel="start"><span class="logo-line-before"><i></i></span> <span class="site-title">It is written</span><span class="logo-line-after"><i></i></span></a></div><p class="site-subtitle"></p></div><div class="site-nav-toggle"> <button><span class="btn-bar"></span><span class="btn-bar"></span><span class="btn-bar"></span></button></div></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i><br> 首页</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i><br> 标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i><br> 分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br> 归档</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i><br> 关于</a></li><li class="menu-item menu-item-search"><a href="javascript:;" class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br> 搜索</a></li></ul><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i></span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"> <input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div></header><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope itemtype="http://schema.org/Article"><div class="post-block"><link itemprop="mainEntityOfPage" href="http://king-xiyu.gitee.io/article/1a004747.html"><span hidden itemprop="author" itemscope itemtype="http://schema.org/Person"><meta itemprop="name" content="King-XiYu"><meta itemprop="description" content=""><meta itemprop="image" content="http://ww1.sinaimg.cn/large/007WurYGgy1ge8nxttd9nj302s02s0si.jpg"></span><span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content="It is written"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">数据结构与算法 (js版) -- 排序</h1><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i></span> <span class="post-meta-item-text">发表于</span> <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-05-11T19:26:14+08:00">2020-05-11</time> <span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-calendar-check-o"></i></span> <span class="post-meta-item-text">更新于&#58;</span> <time title="更新于" itemprop="dateModified" datetime="2020-09-01T08:45:13+08:00">2020-09-01</time></span> <span class="post-category"><span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-folder-o"></i></span> <span class="post-meta-item-text">分类于</span> <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/%E6%8A%80%E6%9C%AF%E6%A0%88/" itemprop="url" rel="index"><span itemprop="name">技术栈</span></a></span> ， <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/%E6%8A%80%E6%9C%AF%E6%A0%88/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">数据结构与算法</span></a></span></span> <span class="post-comments-count"><span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-comment-o"></i></span><a href="/article/1a004747.html#comments" itemprop="discussionUrl"><span class="post-comments-count valine-comment-count" data-xid="/article/1a004747.html" itemprop="commentCount"></span></a></span> <span id="/article/1a004747.html" class="leancloud_visitors" data-flag-title="数据结构与算法 (js版)  -- 排序"><span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-eye"></i></span> <span class="post-meta-item-text">阅读次数&#58;</span><span class="leancloud-visitors-count"></span></span><div class="post-wordcount"><span class="post-meta-item-icon"><i class="fa fa-file-word-o"></i></span> <span class="post-meta-item-text">字数统计&#58;</span> <span title="字数统计">4.9k 字</span> <span class="post-meta-divider">|</span><span class="post-meta-item-icon"><i class="fa fa-clock-o"></i></span> <span class="post-meta-item-text">阅读时长 &asymp;</span> <span title="阅读时长">20 分钟</span></div></div></header><div class="post-body" itemprop="articleBody"><p>排序算法是《数据结构与算法》中最基本的算法之一。</p><p>排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geoqro1171j319o0sib0r.jpg" alt="04dfe113e21841016523bfd126303b24_1644x1026.png"></p><p>参考地址：<a href="https://www.runoob.com/w3cnote/ten-sorting-algorithm.html" target="_blank" rel="noopener">https://www.runoob.com/w3cnote/ten-sorting-algorithm.html</a></p><a id="more"></a><br><p>点击以下图片查看大图：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger44efmwxj31450ggq8k.jpg" alt="0B319B38-B70E-4118-B897-74EFA7E368F9.png"></p><h1 id="性质"><a href="#性质" class="headerlink" title="性质"></a>性质</h1><h2 id="关于时间复杂度"><a href="#关于时间复杂度" class="headerlink" title="关于时间复杂度"></a>关于时间复杂度</h2><p>平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。</p><p>线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；</p><p>O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序</p><p>线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。</p><p>关于稳定性</p><p>稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。</p><p>不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。</p><p>名词解释：</p><ul><li>n：数据规模</li><li>k：”桶”的个数</li><li>In-place：占用常数内存，不占用额外内存</li><li>Out-place：占用额外内存</li><li>稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同</li></ul><h2 id="稳定性"><a href="#稳定性" class="headerlink" title="稳定性"></a>稳定性</h2><p>数组中两个相同的元素再排序完之后，如果相对位置没变就是稳定的，否则就是不稳定的。</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geoqvb4uq3j317s0ownn1.jpg" alt="b8b10bfddc7c932ffbf89943bb74a4b5_1576x896.png"></p><h2 id="内排序与外排序"><a href="#内排序与外排序" class="headerlink" title="内排序与外排序"></a>内排序与外排序</h2><p>排序可以分为内排序和外排序。</p><p><strong>内排序</strong>：在数据内部（内存）完成排序。</p><p><strong>外排序</strong>：当数据量极大时，需要使用外部存储设备进行排序。</p><br><h1 id="简单的排序"><a href="#简单的排序" class="headerlink" title="简单的排序"></a>简单的排序</h1><p>三种最基础、最简单的排序方法：</p><ul><li>冒泡排序</li><li>选择排序</li><li>插入排序</li></ul><p>它们的时间复杂度都为：O(n^2)</p><h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geor0u1lx6g30my075wqv.jpg" alt="33a947c71ad62b254cab62e5364d2813_826x257.jpg"></p><p>实现思路：两两比较，大的向后移动。</p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 冒泡排序</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">bubbleSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">1</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; arr.length - j - <span class="number">1</span>; i++) &#123;</span><br><span class="line">            <span class="comment">// 如果前一个大于后一个就交换</span></span><br><span class="line">            <span class="keyword">if</span> (arr[i] &gt; arr[i + <span class="number">1</span>]) &#123;</span><br><span class="line">                <span class="comment">// 交换</span></span><br><span class="line">                [arr[i], arr[i + <span class="number">1</span>]] = [arr[i + <span class="number">1</span>], arr[i]]</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geos1cerbbg30mj06w7l2.jpg" alt="1c7e20f306ddc02eb4e3a50fa7817ff4_811x248.jpg"></p><p>冒泡排序要频率的两两交换，而选择排序可以先标记出最小的元素，最后再交换，这样可以减少交换的次数。</p><p>特点：每趟循环只执行一次交换操作。</p><p>思路：在每次循环时找出最小的元素，然后标记一下，不执行交换，直到本次循环完之后，把标记的最小的元素放到最前面，然后再找第二小的元素。。</p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 选择排序</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">selectSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 保存每次循环时最小元素的下标</span></span><br><span class="line">    <span class="keyword">let</span> minIndex;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; arr.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="comment">// 设置最小的开始为本次循环第一个元素</span></span><br><span class="line">        minIndex = i</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = i + <span class="number">1</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (arr[minIndex] &gt; arr[j]) &#123;</span><br><span class="line">                minIndex = j</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 把最小的元素交换到开始的位置</span></span><br><span class="line">        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> arr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geossx8k63g30mj0e113f.jpg" alt="91b76e8e4dab9b0cad9a017d7dd431e2_811x505.jpg"></p><p>思路：</p><ol><li>从第2个元素开始向后依次取出一个元素，记作 a</li><li>a 依次和它前面的每一个元素进行比较</li><li>如果前面的某个元素大于 a，那么这个大的元素就向后移一位</li><li>当遇到一个不大于 a 的元素时，就把 a 放到这个元素的后面</li></ol><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 插入排序</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">insertSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> tmp</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 取出第 i 个元素</span></span><br><span class="line">        tmp = arr[i]</span><br><span class="line">        <span class="comment">// 循环前面的元素进行比较</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">var</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">0</span>; j--) &#123;</span><br><span class="line">            <span class="comment">// 如果前面的元素大于这个元素</span></span><br><span class="line">            <span class="keyword">if</span> (arr[j] &gt; tmp) &#123;</span><br><span class="line">                <span class="comment">// 把前面这个元素向后移动一位</span></span><br><span class="line">                arr[j + <span class="number">1</span>] = arr[j]</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 把这个元素放到不小于它的元素后面</span></span><br><span class="line">        arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> arr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>简写：</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 插入排序</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">insertSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 取出第 i 个元素</span></span><br><span class="line">        <span class="keyword">let</span> tmp = arr[i]</span><br><span class="line">        <span class="comment">// 循环前面的元素进行比较</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">var</span> j = i - <span class="number">1</span>; j &gt;= <span class="number">0</span> &amp;&amp; arr[j] &gt; tmp; j--) &#123;</span><br><span class="line">            <span class="comment">// 如果前面的元素大于这个元素,把前面的这个元素向后移动一位</span></span><br><span class="line">            arr[j + <span class="number">1</span>] = arr[j]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 把这个元素放到不小于它的元素后面</span></span><br><span class="line">        arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> arr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br><h1 id="分治"><a href="#分治" class="headerlink" title="分治"></a>分治</h1><p>分治：分而治之。<br>分：将大问题拆分成一个一个的小问题，然后对每个小问题求解。<br>治：再将所有小问题的解合并成最终解。</p><p>分治排序时一般的时间复杂度为：O(nlogn)</p><h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><p>希尔排序（以发明者的名字命名），也称 <code>递减增量</code> 排序算法，是 <code>插入排序</code> 的一种更高效的改进版本。</p><p>实际思路：</p><ol><li>先拆分成N个组的子数组</li><li>对每个子数组进行插入排序，让子数组有序</li><li>再拆分成 N 个子数组</li><li>对每个子数组进行插入排序，让子数组有序</li></ol><p>……直到无法再拆分为止。</p><p>拆分原理：</p><p>第一次的跨度：用数组长度/2</p><p>第二次的跨度：上一次的跨度/2</p><p>直到跨度为0结束</p><p>前提：需要先对插入排序有较深的理解。</p><p><strong>实现思路</strong></p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geps5w4qi9j30xs11g1kx.jpg" alt="3314a70995c7363d2f900fa5a01470ed_1216x1348.png"></p><p>Javascript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">shellSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 计算跨度</span></span><br><span class="line">    <span class="keyword">let</span> gap = <span class="built_in">parseInt</span>(arr.length/<span class="number">2</span>)</span><br><span class="line">    <span class="comment">// 保存临时数据</span></span><br><span class="line">    <span class="keyword">let</span> tmp</span><br><span class="line">    <span class="comment">// 当跨度大于0时（跨度每次减半）</span></span><br><span class="line">    <span class="keyword">while</span>(gap&gt;<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="comment">/* 对每个跨度对应的组执行 “插入排序” */</span></span><br><span class="line">        <span class="comment">// 插入排序是从第2 个元素开始向前面的比较</span></span><br><span class="line">        <span class="comment">// 所以这里开始的元素是 gap （向后一个跨度）即第2个元素</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> i=gap; i&lt;arr.length; i++) &#123;</span><br><span class="line">            <span class="comment">// 保存当前元素</span></span><br><span class="line">            tmp = arr[i]</span><br><span class="line">            <span class="comment">// 对同一跨度组的前面的元素进行比较</span></span><br><span class="line">            <span class="comment">// 如果前一个元素大于这个元素，那么前一个</span></span><br><span class="line">            <span class="comment">// 元素就向后挪一位，直到一个不大于当前元素的就退出循环（不需要再向前比较了）</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">var</span> j=i-gap;j&gt;=<span class="number">0</span> &amp;&amp; tmp&lt;arr[j];j-=gap) &#123;</span><br><span class="line">                arr[j+gap] = arr[j]</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 把当前元素放到不大于它的这个元素的后面</span></span><br><span class="line">            arr[j+gap]=tmp            </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 跨度减小一半</span></span><br><span class="line">        gap = <span class="built_in">parseInt</span>(gap/<span class="number">2</span>)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> arr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><p>归并也使用的是分治的思想，并且可以使用 <code>递归</code> 实现。</p><p>图示：<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsevjny1j319i0x6e50.jpg" alt="6f92326f3277c3d2e3e5d23bfbb29d3d_1638x1194.png"></p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 拆分原数组，一半一半的拆分成左右两个数组</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">mergeSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 当分的只剩一个时直接返回</span></span><br><span class="line">    <span class="keyword">if</span>(arr.length&lt;<span class="number">2</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> arr</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 取中间位置</span></span><br><span class="line">    <span class="keyword">let</span> midPos = <span class="built_in">parseInt</span>(arr.length/<span class="number">2</span>)</span><br><span class="line">    <span class="comment">// 拆分成两个子数组</span></span><br><span class="line">    <span class="keyword">let</span> left = arr.slice(<span class="number">0</span>, midPos)</span><br><span class="line">    <span class="keyword">let</span> right = arr.slice(midPos)</span><br><span class="line">    <span class="comment">// 合并两个分支</span></span><br><span class="line">    <span class="keyword">return</span> merge(mergeSort(left), mergeSort(right))</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 合并两个数组（按升序合并）</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">merge</span>(<span class="params">left, right</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 定义一个额外的数组，用来实现合并,这个数组的长度就是原数组的长度 n,所有空间复杂度是 O(n)</span></span><br><span class="line">    <span class="keyword">let</span> result = []</span><br><span class="line">    <span class="keyword">while</span>(left.length &amp;&amp; right.length) &#123;</span><br><span class="line">        <span class="comment">// 如果左边小就弹出左边的第1个元素放到 result 中，否则弹出右边的第1个元素放到 result 中</span></span><br><span class="line">        <span class="keyword">if</span>(left[<span class="number">0</span>]&lt;right[<span class="number">0</span>]) &#123;</span><br><span class="line">            result.push(left.shift())</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            result.push(right.shift())</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果左边还剩有元素</span></span><br><span class="line">    <span class="keyword">while</span>(left.length) &#123;</span><br><span class="line">        result.push(left.shift())</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(right.length) &#123;</span><br><span class="line">        result.push(right.shift())</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><blockquote><p>引用：<a href="https://www.cnblogs.com/chengxiao/p/6262208.html" target="_blank" rel="noopener">https://www.cnblogs.com/chengxiao/p/6262208.html</a></p></blockquote><p>快速排序，正如其名，比其他分治排序一般要快。</p><p>思路：</p><ol><li>从数组中随便取出一个数，把这个数当成一个“基数”</li><li>循环数组中所有元素和这个“基数”对比，比它小的放在它左边，比它大的放在它右边</li><li>再基数左右两边的元素看成两个子数组，再分别对两个子数组执行快速排序。。</li></ol><p>如何确定哪个数做为“基数”？<br>我们可以使用 “三值取中法” 来确定基数。<br>思路：取数组中第1个、中间和最后一个元素三个值，对这三个数排序，把排在中间的数做为基数。（尽量让这个数是所有值中排序中在中间位置的数）</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger5o6v5whj30yg0hcgwf.jpg" alt="5a1ea8948291c8779139fc41f82ebc09_1240x624.png"></p><p>对剩下的数进行循环处理：小于“基数”的放到左边，大于基数的放到右边</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger5p2cnlhj30to0wi4ed.jpg" alt="8757ae4f2367a92db6ecea89329bf451_1068x1170.png"></p><p>现在基数（6）左边都是小于它的，右边都是大于它的。<br>然后在对基数（6）左右两部分分成两个子数列：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger5puolrsj30tk0co455.jpg" alt="6381657fa1c2b991e56458b7580b2e9d_1064x456.png"></p><p>然后再对左右两个子数列执行上面的过程排序：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger5qyfuhuj317q0kknc3.jpg" alt="2228aff8dd638aa66f0c4351449fbcb8_1574x740.png"></p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span>  <span class="title">quickSort</span>(<span class="params">arr, left, right</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left  &lt;  right) &#123;</span><br><span class="line">        <span class="comment">/****** 1.处理 pivot \*/</span></span><br><span class="line">        <span class="comment">// 计算中间值的下标</span></span><br><span class="line">        <span class="keyword">let</span>  mid  =  <span class="built_in">Math</span>.floor((left  +  right) /  <span class="number">2</span>)</span><br><span class="line">        <span class="comment">// 左和中进行比较，大的放中间</span></span><br><span class="line">        <span class="keyword">if</span>(arr[left] &gt;  arr[mid]) &#123;</span><br><span class="line">            [arr[left],arr[mid]] = [arr[mid],arr[left]]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 中和右进行比较，大的放右边</span></span><br><span class="line">        <span class="keyword">if</span>(arr[mid] &gt; arr[right]) &#123;</span><br><span class="line">            [arr[right],arr[mid]] = [arr[mid],arr[right]]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 左和中进行比较，大的放中间</span></span><br><span class="line">        <span class="keyword">if</span>(arr[left] &gt;  arr[mid]) &#123;</span><br><span class="line">            [arr[left],arr[mid]] = [arr[mid],arr[left]]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 把中间的（pivot）放到倒数第2个位置</span></span><br><span class="line">        [arr[mid],arr[right<span class="number">-1</span>]] = [arr[right<span class="number">-1</span>],arr[mid]]</span><br><span class="line">    </span><br><span class="line">        <span class="comment">/* 2.双向循环把小的放到 pivot 左边，大的放到 pivot 右边 */</span></span><br><span class="line">        <span class="keyword">let</span>  pivot  =  right<span class="number">-1</span>, <span class="comment">// pivot 坐标</span></span><br><span class="line">        i  =  left, <span class="comment">// 左指针</span></span><br><span class="line">        j  =  right  -  <span class="number">1</span>  <span class="comment">// 右指针</span></span><br><span class="line">        <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">            <span class="comment">//左指针小于 pivot 时元素不动继续向后移动指针</span></span><br><span class="line">            <span class="keyword">while</span> (arr[++i] &lt;  arr[pivot]) &#123; &#125;</span><br><span class="line">            <span class="comment">// 右指针大于 pivot 时元素不动继续向前移动指针</span></span><br><span class="line">            <span class="keyword">while</span> (j &gt; left  &amp;&amp;  arr[--j] &gt;  arr[pivot]) &#123; &#125;</span><br><span class="line">            <span class="comment">// 如果左右指针没有相遇就交换，否则退出循环</span></span><br><span class="line">            <span class="keyword">if</span> (i  &lt;  j) &#123;</span><br><span class="line">                [arr[i],arr[j]] = [arr[j],arr[i]]</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 将 pivot 放到中间，此时 pivot 左边都是小于它的数，右边都是大于它的数</span></span><br><span class="line">        <span class="keyword">if</span> (i  &lt;  right) &#123;</span><br><span class="line">            [arr[i], arr[right<span class="number">-1</span>]] = [arr[right<span class="number">-1</span>],arr[i]]</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 根据 pivot 拆分成左右两个子数组继续快速排序</span></span><br><span class="line">        quickSort(arr, left, i<span class="number">-1</span>)</span><br><span class="line">        quickSort(arr, i+<span class="number">1</span>, right)</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span>  arr</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br><h1 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h1><p>二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。</p><h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><blockquote><p>引用：<a href="https://www.cnblogs.com/chengxiao/p/6129630.html" target="_blank" rel="noopener">https://www.cnblogs.com/chengxiao/p/6129630.html</a></p></blockquote><p>堆的概念：</p><ol><li>堆就是一个棵二叉树（每个节点 <code>最多有两个子节点</code> 的结构）</li><li>大顶堆：每个节点的值都比子节点的值大（所以，堆顶元素肯定是最大的）</li><li>大顶堆：每个节点的值都比子节点的值小（所以，堆顶元素肯定是最小的）</li></ol><p>堆可以保存在数组中，在数组中的特点：<br>第 i 个节点的 左子节点下标是 2i+1<br>右子节点下标是 2i+2</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsljb9anj31ds0lkn0v.jpg" alt="1024555-20161217182750011-675658660.png"></p><p>再数组中使用编号来表示：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsmj3pn4j30u805odid.jpg" alt="f908d22f5fa1b310a99ffa0bb8823c5c_1088x204.png"></p><p>堆排序的实现思路：</p><ol><li>先把数组构造成一个大顶堆</li><li>把顶堆元素（最大）放到数组最后</li><li>把数组中除了最后一个元素（已经排好序的最大元素）之外的数组当成一个数组，重新构造成一个大顶堆</li><li>再把顶堆（下标为0）元素（第二大）放到数组倒数第二的位置以此类推……</li></ol><h3 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h3><h4 id="步骤一"><a href="#步骤一" class="headerlink" title="步骤一"></a>步骤一</h4><p><strong>构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。</strong></p><ol><li><p>假设给定无序序列结构如下<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsuibhxrj30ji0i6myd.jpg" alt="1024555-20161217192038651-934327647.png"></p></li><li><p>此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepswvll78j31bg0iyacd.jpg" alt="1024555-20161217192209433-270379236.png"></p></li><li><p>找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsxxlsbyj31ao0jeacb.jpg" alt="1024555-20161217192854636-1823585260.png"></p></li><li><p>这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gepsyd3qkuj31bs0ia41a.jpg" alt="1024555-20161217193347886-1142194411.png"></p></li></ol><p>此时，我们就将一个无需序列构造成了一个大顶堆。</p><h4 id="步骤二"><a href="#步骤二" class="headerlink" title="步骤二"></a>步骤二</h4><p><strong>将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。</strong></p><ol><li>将堆顶元素9和末尾元素4进行交换<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gept1bkas5j31e00i6act.jpg" alt="1024555-20161217194207620-1455153342.png"></li><li>重新调整结构，使其继续满足堆定义<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gept231uwvj31as0hgq5m.jpg" alt="1024555-20161218153110495-1280388728.png"></li><li>再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gept2cyyvij31ay0huwge.jpg" alt="1024555-20161218152929339-1114983222.png"></li><li>后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序<img src="http://ww1.sinaimg.cn/large/007WurYGgy1gept2qhx4cj30lq0j8wfl.jpg" alt="1024555-20161218152348229-935654830.png"></li></ol><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 堆排序</span></span><br><span class="line"><span class="keyword">let</span> len; <span class="comment">// 定义变量</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">heapSort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 保存数组的长度</span></span><br><span class="line">    len = arr.length</span><br><span class="line">    <span class="comment">// 1. 先把数组构造成一个大顶堆，从最后一个“非叶子节点”（len/2-1)构造大顶堆</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="built_in">Math</span>.floor(len / <span class="number">2</span>) - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</span><br><span class="line">        <span class="comment">// 调整节点为大顶</span></span><br><span class="line">        heapify(arr, i)</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 2. 依次把根节点移动到数组最后，并重新调整大顶堆</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = arr.length - <span class="number">1</span>; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">        <span class="comment">// 把第一个元素（最大的）交换到最后</span></span><br><span class="line">        [arr[<span class="number">0</span>], arr[i]] = [arr[i], arr[<span class="number">0</span>]]</span><br><span class="line">        <span class="comment">// 长度减少（以后省略最后一个元素）</span></span><br><span class="line">        len--</span><br><span class="line">        <span class="comment">// 从根节点开始重新调整剩余元素为大顶堆</span></span><br><span class="line">        heapify(arr, <span class="number">0</span>)</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 调整一个节点为大堆节点</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">heapify</span>(<span class="params">arr, i</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 获取这个节点的左右子节点坐标</span></span><br><span class="line">    <span class="keyword">let</span> left = <span class="number">2</span> * i + <span class="number">1</span>,</span><br><span class="line">        right = <span class="number">2</span> * i + <span class="number">2</span>,</span><br><span class="line">        largest = i   <span class="comment">// 默认节点为最大元素</span></span><br><span class="line">    <span class="comment">// 如果有左子节点，并且左子节点大于父节点</span></span><br><span class="line">    <span class="keyword">if</span> (left &lt; len &amp;&amp; arr[left] &gt; arr[largest]) &#123;</span><br><span class="line">        <span class="comment">// 标记左子节点更大</span></span><br><span class="line">        largest = left</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果有右子节点，并且右子节点大于父节点</span></span><br><span class="line">    <span class="keyword">if</span> (right &lt; len &amp;&amp; arr[right] &gt; arr[largest]) &#123;</span><br><span class="line">        <span class="comment">// 标记右子节点更大</span></span><br><span class="line">        largest = right</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 如果标记最大的元素不是父节点</span></span><br><span class="line">    <span class="keyword">if</span> (i != largest) &#123;</span><br><span class="line">        <span class="comment">// 那么父节点和大的子节点交换</span></span><br><span class="line">        [arr[i], arr[largest]] = [arr[largest], arr[i]]</span><br><span class="line">        <span class="comment">// 对交换之后的节点再次调整</span></span><br><span class="line">        heapify(arr, largest)</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">let</span> abc = [<span class="number">4</span>,<span class="number">6</span>,<span class="number">8</span>,<span class="number">5</span>,<span class="number">9</span>]</span><br><span class="line">heapSort(abc)</span><br><span class="line"><span class="built_in">console</span>.log(abc);</span><br></pre></td></tr></table></figure><br><h1 id="线性时间排序"><a href="#线性时间排序" class="headerlink" title="线性时间排序"></a>线性时间排序</h1><p>以下三种排序都使用了“桶”来进行排序：</p><ul><li>基数排序：根据键值的每位数字来分配桶；</li><li>计数排序：每个桶只存储单一键值；</li><li>桶排序：每个桶存储一定范围的数值；</li></ul><h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geptlnm66fg30s40fhdmw.gif" alt="3c7ddb59df2d21b287e42a7b908409cb_1012x557.gif"></p><p>优点：速度快<br>缺点：需要使用更多的额外空间来进行存储，比如：如果是排序1<del>9之间的数字，那么只需要创建一个10个元素数组即可，但是如果要对1</del>1000000之间的数字进行排序，那么就要创建 1000000个元素的数组，而且还可能造成浪费，比如：对这个数组排序：1,4,1000000,4,63,4，为了容纳需要创建拥有1000000个元素的数组，但这些数组中大多数元素是空的，所以浪费。</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1geptmam205j30nw0dmahk.jpg" alt="5a59e5e72c9fd17c94bd012a2874629a_860x490.png"></p><p>更好办法：基数排序，可以用拥有10个元素的数组排序更大范围的数字。</p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 计数排序</span></span><br><span class="line"><span class="comment">// 参数二： 数组中最大元素的值</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">countSort</span>(<span class="params">arr, maxValue</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 1. 创建一个拥有 maxValue+1 个元素的数组</span></span><br><span class="line">    <span class="keyword">let</span> tmpArr = <span class="keyword">new</span> <span class="built_in">Array</span>(maxValue + <span class="number">1</span>)</span><br><span class="line">    <span class="comment">// 2. 把原数组中的数当作下标加到这个数组中</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">        <span class="comment">// 如果数组中对应的下标的值是 null 时（默认都是 undefined）</span></span><br><span class="line">        <span class="keyword">if</span> (tmpArr[arr[i]]) &#123;</span><br><span class="line">            tmpArr[arr[i]]++</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 如果已经有了值就 +1</span></span><br><span class="line">            tmpArr[arr[i]] = <span class="number">1</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 依次放回原数组</span></span><br><span class="line">    arr.length = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 3. 从桶里面从第一个开始依次拿出来放到原数组中</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">1</span>; i &lt;= tmpArr.length; i++) &#123;</span><br><span class="line">        <span class="keyword">while</span> (tmpArr[i] &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            arr.push(i)</span><br><span class="line">            tmpArr[i]--</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">let</span> abc = [<span class="number">3</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">4</span>, <span class="number">7</span>, <span class="number">9</span>, <span class="number">9</span>, <span class="number">5</span>, <span class="number">4</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">7</span>, <span class="number">9</span>, <span class="number">5</span>, <span class="number">6</span>]</span><br><span class="line">countSort(abc, <span class="number">9</span>)</span><br><span class="line"><span class="built_in">console</span>.log(abc) <span class="comment">// [1, 2, 2, 3, 4, 4, 4,5, 5, 5, 6, 6, 7, 7,9, 9, 9]</span></span><br></pre></td></tr></table></figure><h2 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h2><p>计数排序在对大数进行排序时需要创建一个非常大的额外的数组来容纳这些数，所以非常浪费空间。</p><p>基数排序：无论多大的数进行排序，10个空格的数组即可。</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger34e60kpg30s40fywic.gif" alt="6690b1054909755ffcca96feb7a4d3ec_1012x574.gif"></p><p>扩展：如何取出一个数字的某一位置数字来：</p><p>取个位：parseInt(num % 10 / 1)</p><p>取十位： parseInt(num % 100 / 10)</p><p>取百位： parseInt(num % 1000 / 10)</p><p>…</p><p>JavaScript代码</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 基数排序</span></span><br><span class="line"><span class="keyword">let</span> arr = [<span class="number">9</span>, <span class="number">11</span>, <span class="number">101</span>, <span class="number">1314</span>, <span class="number">23</span>, <span class="number">56</span>, <span class="number">34</span>, <span class="number">76</span>, <span class="number">334</span>, <span class="number">11</span>, <span class="number">999</span>, <span class="number">65</span>, <span class="number">11111</span>, <span class="number">1</span>]</span><br><span class="line"><span class="comment">// max： 数组中最大的数是几位的，比如， 99 就是2位填2，999是3位</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">radixSort</span>(<span class="params">arr, max</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 1. 创建 10 个桶</span></span><br><span class="line">    <span class="keyword">let</span> buckets = <span class="keyword">new</span> <span class="built_in">Array</span>(<span class="number">10</span>)</span><br><span class="line">    <span class="comment">// 2. 开始取个位、十位、百位。。。</span></span><br><span class="line">    <span class="keyword">let</span> mod = <span class="number">10</span>    <span class="comment">// 取模用的</span></span><br><span class="line">    <span class="keyword">let</span> dev = <span class="number">1</span>     <span class="comment">// 用来除的</span></span><br><span class="line">    <span class="keyword">let</span> tmp <span class="comment">// 保存暂时数据</span></span><br><span class="line">    </span><br><span class="line">	<span class="built_in">console</span>.time(<span class="string">'基数排序耗时'</span>);</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; max; i++) &#123;</span><br><span class="line">        <span class="comment">// 循环数组中每个数取每个数的个位/十位/百位...</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">            <span class="comment">// 计算得出个位、十位或百位...</span></span><br><span class="line">            tmp = <span class="built_in">parseInt</span>(arr[j] % mod / dev)</span><br><span class="line">            <span class="comment">// 如果这个桶是空就初始化为一个空数组</span></span><br><span class="line">            <span class="keyword">if</span> (buckets[tmp] == <span class="literal">undefined</span>) &#123;</span><br><span class="line">                buckets[tmp] = []</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 把这个数作为下标放到对应的桶中</span></span><br><span class="line">            buckets[tmp].push(arr[j])</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 从第0个桶开始依次向外取出来元素</span></span><br><span class="line">        <span class="keyword">let</span> pos = <span class="number">0</span> <span class="comment">// 向原数组放的下标</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">10</span>; i++) &#123;</span><br><span class="line">            <span class="comment">// 只要桶里还有元素就一直向外拿</span></span><br><span class="line">            <span class="keyword">while</span> (buckets[i] !== <span class="literal">undefined</span> &amp;&amp; buckets[i].length &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="comment">// 取出桶中的第1个元素依次放回原数组</span></span><br><span class="line">                arr[pos++] = buckets[i].shift()</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 把取模和相除的数扩展10位</span></span><br><span class="line">        mod *= <span class="number">10</span></span><br><span class="line">        dev *= <span class="number">10</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">console</span>.timeEnd(<span class="string">'基数排序耗时'</span>);</span><br><span class="line">    <span class="keyword">return</span> arr;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">// 数组中最大的数是几位的就填几位的</span></span><br><span class="line">radixSort(arr, <span class="number">5</span>)</span><br><span class="line"><span class="built_in">console</span>.log(arr);</span><br></pre></td></tr></table></figure><p>简写为：</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 基数排序</span></span><br><span class="line"><span class="comment">// max： 数组中最大的数是几位的，比如， 99 就是2位填2，999是3位</span></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">radixSort</span>(<span class="params">arr, max</span>) </span>&#123;</span><br><span class="line">    <span class="comment">// 1. 创建 10 个桶</span></span><br><span class="line">    <span class="keyword">let</span> buckets = <span class="keyword">new</span> <span class="built_in">Array</span>(<span class="number">10</span>)</span><br><span class="line">    <span class="comment">// 2. 开始取个位、十位、百位。。。</span></span><br><span class="line">    <span class="keyword">let</span> mod = <span class="number">10</span>    <span class="comment">// 取模用的</span></span><br><span class="line">    <span class="keyword">let</span> dev = <span class="number">1</span>     <span class="comment">// 用来除的</span></span><br><span class="line">    <span class="keyword">let</span> tmp <span class="comment">// 保存暂时数据</span></span><br><span class="line"></span><br><span class="line">    <span class="built_in">console</span>.time(<span class="string">'排序耗时'</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; max; i++) &#123;</span><br><span class="line">        <span class="comment">// 循环数组中每个数取每个数的个位/十位/百位...</span></span><br><span class="line">        <span class="comment">// mod *= 10, dev *= 1 把取模和相除的数扩展10位</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> j = <span class="number">0</span>; j &lt; arr.length; j++, mod *= <span class="number">10</span>, dev *= <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="comment">// 计算得出个位、十位或百位...</span></span><br><span class="line">            tmp = <span class="built_in">parseInt</span>(arr[j] % mod / dev)</span><br><span class="line">            <span class="comment">// 如果这个桶是空就初始化为一个空数组</span></span><br><span class="line">            <span class="keyword">if</span> (buckets[tmp] == <span class="literal">undefined</span>) &#123;</span><br><span class="line">                buckets[tmp] = []</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 把这个数作为下标放到对应的桶中</span></span><br><span class="line">            buckets[tmp].push(arr[j])</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 从第0个桶开始依次向外取出来元素</span></span><br><span class="line">        <span class="keyword">let</span> pos = <span class="number">0</span> <span class="comment">// 向原数组放的下标</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; <span class="number">10</span>; i++) &#123;</span><br><span class="line">            <span class="comment">// 只要桶里还有元素就一直向外拿</span></span><br><span class="line">            <span class="keyword">while</span> (buckets[i] !== <span class="literal">undefined</span> &amp;&amp; buckets[i].length &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="comment">// 取出桶中的第1个元素依次放回原数组</span></span><br><span class="line">                arr[pos++] = buckets[i].shift()</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">console</span>.timeEnd(<span class="string">'排序耗时'</span>);</span><br><span class="line">    <span class="keyword">return</span> arr;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><br><h1 id="扩展小技巧"><a href="#扩展小技巧" class="headerlink" title="扩展小技巧"></a>扩展小技巧</h1><h2 id="检测代码段耗时"><a href="#检测代码段耗时" class="headerlink" title="检测代码段耗时"></a>检测代码段耗时</h2><p><code>console.time()</code> 和 <code>console.timeEnd()</code>，用来显示代码的运行时间。</p><p>JS代码：</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">console</span>.time(<span class="string">'排序耗时'</span>);</span><br><span class="line">... <span class="comment">// 代码段</span></span><br><span class="line"><span class="built_in">console</span>.timeEnd(<span class="string">'排序耗时'</span>);</span><br></pre></td></tr></table></figure><p>例如：</p><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">test1</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">    <span class="built_in">console</span>.time(<span class="string">'t1'</span>)</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; <span class="number">1000000</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (i == <span class="number">99</span>) &#123;</span><br><span class="line">            <span class="keyword">var</span> temp = <span class="number">1</span></span><br><span class="line">            <span class="keyword">continue</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">console</span>.timeEnd(<span class="string">'t1'</span>)</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">test2</span>(<span class="params"></span>) </span>&#123;</span><br><span class="line">    <span class="built_in">console</span>.time(<span class="number">2</span>)</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; <span class="number">1000000</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (i == <span class="number">99</span>) &#123;</span><br><span class="line">            <span class="keyword">var</span> temp = <span class="number">1</span></span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">console</span>.timeEnd(<span class="number">2</span>)</span><br><span class="line">&#125;</span><br><span class="line">test1() <span class="comment">// 3.289ms</span></span><br><span class="line">test2() <span class="comment">// 0.014ms</span></span><br></pre></td></tr></table></figure><p>演示结果：</p><p><img src="http://ww1.sinaimg.cn/large/007WurYGgy1ger5g91o8oj30cw01wq2s.jpg" alt="Snipaste_2020-05-13_21-36-01.png"></p></div><footer class="post-footer"><div class="post-tags"><a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 数据结构与算法</a></div><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/article/fb0ed55d.html" rel="next" title="数据结构与算法 (js版)  -- 算法分析"><i class="fa fa-chevron-left"></i> 数据结构与算法 (js版) -- 算法分析</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"> <a href="/article/2a16eda9.html" rel="prev" title="数据结构与算法 (js版)  -- 数据结构">数据结构与算法 (js版) -- 数据结构<i class="fa fa-chevron-right"></i></a></div></div></footer></div></article><div class="post-spread"></div></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span><span class="sidebar-toggle-line sidebar-toggle-line-middle"></span><span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap"> 文章目录</li><li class="sidebar-nav-overview" data-target="site-overview-wrap"> 站点概览</li></ul><section class="site-overview-wrap sidebar-panel"><div class="site-overview"><div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person"> <img class="site-author-image" itemprop="image" src="http://ww1.sinaimg.cn/large/007WurYGgy1ge8nxttd9nj302s02s0si.jpg" alt="King-XiYu"><p class="site-author-name" itemprop="name">King-XiYu</p><p class="site-description motion-element" itemprop="description">有志者事竟成</p></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"> <a href="/archives/"><span class="site-state-item-count">37</span> <span class="site-state-item-name">日志</span></a></div><div class="site-state-item site-state-categories"> <a href="/categories/index.html"><span class="site-state-item-count">11</span> <span class="site-state-item-name">分类</span></a></div><div class="site-state-item site-state-tags"> <a href="/tags/index.html"><span class="site-state-item-count">10</span> <span class="site-state-item-name">标签</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="https://gitee.com/King-XiYu" target="_blank" title="Gitee"><i class="fa fa-fw fa-hand-o-right"></i> Gitee</a></span><span class="links-of-author-item"><a href="https://github.com/King-XiYu" target="_blank" title="GitHub"><i class="fa fa-fw fa-github"></i> GitHub</a></span></div><div class="links-of-blogroll motion-element links-of-blogroll-inline"><div class="links-of-blogroll-title"><i class="fa fa-fw fa-link"></i> Links</div><ul class="links-of-blogroll-list"><li class="links-of-blogroll-item"> <a href="https://www.baidu.com/" title="度娘" target="_blank">度娘</a></li><li class="links-of-blogroll-item"> <a href="https://www.google.com/" title="Google" target="_blank">Google</a></li></ul></div></div></section><section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#性质"><span class="nav-number">1.</span> <span class="nav-text">性质</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#关于时间复杂度"><span class="nav-number">1.1.</span> <span class="nav-text">关于时间复杂度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#稳定性"><span class="nav-number">1.2.</span> <span class="nav-text">稳定性</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#内排序与外排序"><span class="nav-number">1.3.</span> <span class="nav-text">内排序与外排序</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#简单的排序"><span class="nav-number">2.</span> <span class="nav-text">简单的排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#冒泡排序"><span class="nav-number">2.1.</span> <span class="nav-text">冒泡排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#选择排序"><span class="nav-number">2.2.</span> <span class="nav-text">选择排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#插入排序"><span class="nav-number">2.3.</span> <span class="nav-text">插入排序</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#分治"><span class="nav-number">3.</span> <span class="nav-text">分治</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#希尔排序"><span class="nav-number">3.1.</span> <span class="nav-text">希尔排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#归并排序"><span class="nav-number">3.2.</span> <span class="nav-text">归并排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#快速排序"><span class="nav-number">3.3.</span> <span class="nav-text">快速排序</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二叉树"><span class="nav-number">4.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#堆排序"><span class="nav-number">4.1.</span> <span class="nav-text">堆排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#实现"><span class="nav-number">4.1.1.</span> <span class="nav-text">实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#步骤一"><span class="nav-number">4.1.1.1.</span> <span class="nav-text">步骤一</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#步骤二"><span class="nav-number">4.1.1.2.</span> <span class="nav-text">步骤二</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#线性时间排序"><span class="nav-number">5.</span> <span class="nav-text">线性时间排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#计数排序"><span class="nav-number">5.1.</span> <span class="nav-text">计数排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#基数排序"><span class="nav-number">5.2.</span> <span class="nav-text">基数排序</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#扩展小技巧"><span class="nav-number">6.</span> <span class="nav-text">扩展小技巧</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#检测代码段耗时"><span class="nav-number">6.1.</span> <span class="nav-text">检测代码段耗时</span></a></li></ol></li></ol></div></div></section><div class="back-to-top"><i class="fa fa-arrow-up"></i> <span id="scrollpercent"><span>0</span>%</span></div></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><div class="copyright">&copy; <span itemprop="copyrightYear">2020</span><span class="with-love"><i class="fa fa-user"></i></span> <span class="author" itemprop="copyrightHolder">宇宙特别帅</span></div></div></footer></div><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script><script type="text/javascript" src="/lib/canvas-nest/canvas-nest.min.js"></script><script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script><script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script><script src="//cdn.jsdelivr.net/npm/valine/dist/Valine.min.js"></script><script type="text/javascript">
    var GUEST = ['nick','mail','link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item=>{
      return GUEST.indexOf(item)>-1;
    });
    new Valine({
        el: '#comments' ,
        verify: false,
        notify: true,
        appId: '9DODHXKj6rr1cK4oO07iVBX3-gzGzoHsz',
        appKey: 'aJaxxns4VN5WV9nMimT9aSb1',
        placeholder: 'ヾﾉ≧∀≦)o 来呀！吐槽一番吧！',
        avatar:'mp',
        guest_info:guest,
        pageSize:'10' || 10,
    });
  </script><script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "./public/search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script><script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script><script>AV.initialize("9DODHXKj6rr1cK4oO07iVBX3-gzGzoHsz","aJaxxns4VN5WV9nMimT9aSb1")</script><script>function showTime(e){var t=new AV.Query(e),c=[],u=$(".leancloud_visitors");u.each(function(){c.push($(this).attr("id").trim())}),t.containedIn("url",c),t.find().done(function(e){var t=".leancloud-visitors-count";if(0!==e.length){for(var n=0;n<e.length;n++){var o=e[n],i=o.get("url"),s=o.get("time"),r=document.getElementById(i);$(r).find(t).text(s)}for(n=0;n<c.length;n++){i=c[n],r=document.getElementById(i);var l=$(r).find(t);""==l.text()&&l.text(0)}}else u.find(t).text(0)}).fail(function(e,t){console.log("Error: "+t.code+" "+t.message)})}function addCount(i){var e=$(".leancloud_visitors"),s=e.attr("id").trim(),r=e.attr("data-flag-title").trim(),t=new AV.Query(i);t.equalTo("url",s),t.find({success:function(e){if(0<e.length){var t=e[0];t.fetchWhenSave(!0),t.increment("time"),t.save(null,{success:function(e){$(document.getElementById(s)).find(".leancloud-visitors-count").text(e.get("time"))},error:function(e,t){console.log("Failed to save Visitor num, with error message: "+t.message)}})}else{var n=new i,o=new AV.ACL;o.setPublicReadAccess(!0),o.setPublicWriteAccess(!0),n.setACL(o),n.set("title",r),n.set("url",s),n.set("time",1),n.save(null,{success:function(e){$(document.getElementById(s)).find(".leancloud-visitors-count").text(e.get("time"))},error:function(e,t){console.log("Failed to create")}})}},error:function(e){console.log("Error:"+e.code+" "+e.message)}})}$(function(){var e=AV.Object.extend("Counter");1==$(".leancloud_visitors").length?addCount(e):1<$(".post-title-link").length&&showTime(e)})</script><script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.4/clipboard.min.js"></script><script type="text/javascript" src="/js/src/clipboard-use.js"></script></body></html>